题意简述
给你一个含变量的式子,所有的系数为常数,定义模糊的部分按任意次序计算。如:既可以先算 , 也可以先算。
给你的初值,求算式的最大值。
样例:为了方便描述,用括号隔开
计算顺序为:
答案为:
进入正题
这道题可以贪心解决,我们不难想到,系数越小,我们越先算(减法系数取负)。
下面给出证明:
结论1:当系数相同时,与的顺序对答案无影响。
证明:若原式有这样一个部分:
先算前部分:
先算后部分:
结果是相等的,同时,改变后的值也相等,证毕。
结论2:当系数不同时,系数小的先算
证明:考虑4个式子:()
先讨论第一个式子,其余同理。
先算左式:
先算右式:
两式作差:
当,,即先算左式更优,刚好是小系数。
同理。
知道贪心策略后,代码实现不难,模拟求出系数与式子是还是。
最后排序算出答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
int a,len;
int k , f;
struct node{
int a_i , fr;
operator < ( const node &x ) {
return a_i < x.a_i;
}
}c[ 100005 ];
char s[ 1000005 ];
signed main( ) {
scanf("%lld\n",&a);scanf("%s",s);
int len = strlen( s );
for( int i = 0 ; i < len ; i ++ ) {
f = 1;
if( s[ i ] == '-' ) f = -1 , i ++;
if( s[ i ] == '+' && ( s[ i + 1 ] != '+' || ( s[ i + 1 ] == '+' && s[ i + 2 ] == '+' ) ) ) i ++;
if( '0' <= s[ i ] && s[ i ] <= '9' ) {
k ++;
while( '0' <= s[ i ] && s[ i ] <= '9' ) {
c[ k ].a_i = c[ k ].a_i * 10 + s[ i ] - '0';
i ++;
}
i ++; c[ k ].a_i *= f;
if( s[ i ] == '+' ) c[ k ].fr = 1;
i += 2;
}
else if( s[ i ] == '+' ) {
c[ ++ k ].a_i = f;
c[ k ].fr = 1;
i += 2;
}
else if( s[ i ] == 'a' ) {
c[ ++ k ].a_i = f;
i += 2;
}
}
/*for( int i = 1 ; i <= k ; i ++ )
printf("%lld %lld\n",c[ i ].a_i,c[ i ].fr);*/
sort( c + 1 , c + k + 1 );
int Ans = 0;
for( int i = 1 ; i <= k ; i ++ ) {
Ans = Ans + c[ i ].a_i * ( c[ i ].fr ? a + 1 : a );
a ++;
}
printf("%lld",Ans);
return 0;
}